/*
 *    Plurals
 *
 *    Author:    S.C.Merrall
 *
 *    File:      mp_mem_mgmt.m
 *
 *    Contents:    	alloc_plural
 *			mp_free_plurals		visible
 *			extend_plural_space
 *			find_space
 *                      init_mem
 *
 *    Description: 	   These functions manage the PE's local memory
 *			that is the plural-space and the 
 *			heap space keeping the free information updated. 
 *			They create functions with handles specifiued in 
 *			mp_plurals.h and mp_plurals.c
 *
 *    Change History:
 *
 *    Date   Name Comment
 *  -------- ---- -------
 *  29:01:91 SCM  Created
 *  13:02:91 SCM  Sussed the abstraction
 *  19:02:91 SCM  Changed to come in line with renamed object system
 *  15:04:91 SCM  Changed to allow heap allocation in 32-bit blocks
 *  16:06:91 SCM  Moved definition of scratch to mp_io.m
 *  21:05:91 SCM  alloc_plural no longer visible, wrapped by make_plural
 *  20:01:92 SCM  Modified to use paired processors
 *  26:03:92 SCM  free_plural axed.
 *  26:03:92 SCM  mp_free_plurals, called by fe_gc, updates entire plural space
 *  27:03:92 SCM  memory management information now in reverse "sense"
 *  08:04:92 SCM  plural_space visible to front end for temp plural space!
 *  10:04:92 SCM  Implementing a fe driven stack system for GC protect.
 *  27:05:92 SCM  Began converting to rectangular allocator.
 *
 */

/*    To be consistent with Eulisp the plural structure will not
 *    contain LispObjects but will contain a pointer to a LispObject
 *    which will be allocated from the heap space on the PE. 
 *       The plural space will be allocated from the low end of the
 *    local memory and the heap space from the high end. This scheme
 *    has the advantage that the objects in the plural space are all
 *    the same size.
 *       At this stage I am assuming that each elements of a
 *    plural's LispObject will be on the same PE's local memory.
 *    Since we have only 16K of local memory this gives us a high
 *    bit we can hopefully use to indicate free memory. 
 */

/* Include Files */
/* ======= ===== */

#include <mpl.h>
#include "proc_pair.h"
#include "seq_net.h"
#include <stdio.h>

#include "mp_eubang.h"

/*  #include "constant.h" inside mp_eubang.h, which is now included because
 *  we have a visible function
 */

#include "mp_object.h"
#include "mp_debug_off.h"
#include "mp_mem_mgmt.h"
#include "mp_gc.h"

/* External Variables */
/* ======== ========= */

extern object MPC_chain;  /*  This variable only used in this file so there 
			   *  doesn't seem to be too much point in putting
			   *  it in a header
			   */

/* Global Variables */
/* ====== ========= */

plural heap_header  heap_memory[MEMORY_SIZE];   /*  Reserve MEMORY_SIZE 32-bit
                                                 *  words of memory
                                                 */

/* plural natural plural_memory[] = (plural natural *plural) &heap_memory[0]; */

plural natural *plural plural_memory;

                                          /*  Plural space is allocated 
					   *  in 16-bit blocks
					   */

visible natural plural_space = TOP;       /*  Top of plural space. This is
                                           *  always the same on all PEs
                                           *  hence a singular value. 
                                           */

visible plural natural  heap_space=0;     /*  Bottom of heap space. Varies
                                           *  between PE's so a plural
                                           *  value. 
					   */

visible natural stack_base = TOP;	  /*  For the purposes of GC protection
					   *  we need to be able to stack all 
					   *  the active things we are holding
					   *  in mid operation. We use the
					   *  plural space as this stack and
					   *  modify the collector and
					   *  and allocator.
					   */

/*----------------------------------------------------------------------------*
 * Function   : extend_plural_space
 *
 * Parameters : none
 *
 * Description: Extends the plural space by one slot initialising the 
 *		space management data at the same time. The slot on
 *		each PE is marked as free, having its high bit set, the
 *		remaining bits indicating how taller column of free PEs
 *		(for that slot) it is at the bottom of.
 *
 * Result     : natural:	FAIL    - heap space and plural space clashed
 *				SUCCESS - plural space successfully extended
 *---------------------------------------------------------------------------*/

#ifdef __STDC__

natural extend_plural_space( void ) 

#else

natural extend_plural_space( )

#endif

{
  int aok = TRUE;
DBG_CALL("extend_plural_space");
DBG_ARGS(fprintf(dbg,"void"));

  /*  On entry the active set should be "all"
   *  If any of the PE's plural and heap spaces are about to clash we 
   *  cannot extend. */
  
  PP_on_set() {
    
    if (!space_to_grow(sizeof(natural))) {

      fprintf(stderr,"extend_plural_space:No Space, trying back end GC\n");
      mp_gc();
    }
    
    if (!space_to_grow(sizeof(natural))) {

DBG_FAIL(fprintf(dbg,"FAIL: Still No Space after mp-gc"));
      aok = FALSE;
    }
    else {  
      
      plural_memory[plural_space--] = (plural natural) (PP_iyproc+FREE_FLAG+1);
    }
  }
   
  if (!aok) return FAIL;
DBG_EXIT(fprintf(dbg,"SUCCESS: plural_space=%u",plural_space));
  return (natural) SUCCESS;
}


/*----------------------------------------------------------------------------*
 * Function   : update_mgmt_data
 *
 * Parameters : int offset:	The slice of plural space to updat
 *		int width:	The width of theallocated rectangle
 *		int height:	The height of the allocated rectangle
 *		int br_x:	X co-ord of bottom right corner of rectangle
 *		int br_y:@	Y co-ord of bottom right corner of rectangle
 *
 * Description: The specified rectangle has just been allocated in the offset
 *		slice of the plural space. The contents need to be set to NIL
 *		and the management data updated where appropriate
 *
 * Result     : void
 *---------------------------------------------------------------------------*/

#ifdef __STDC__

void update_mgmt_data( int offset, int width, int height, int br_x, int br_y )

#else

void update_mgmt_data( offset,  width,  height,  br_x,  br_y )

int offset;
int width;
int height;
int br_x;
int br_y;

#endif

{
  plural natural mgmt_data;
  plural natural bottom_edge;
DBG_CALL("update_mgmt_data");
DBG_ARGS(fprintf(dbg,"offset=%d, width=%d, height=%d, br_x=%d, br_y=%d",offset,width,height,br_x,br_y));

  bottom_edge = (mgmt_data=(plural_memory[offset] & (~FREE_FLAG))) >= height;

  if ((PP_ixproc > (br_x - width))  && (PP_ixproc <= br_x) &&
      (PP_iyproc > (br_y - height)) && (PP_iyproc <= br_y))
    
    plural_memory[offset] = NIL;

  if ((PP_ixproc >= ((1 + br_x) - width))  && (PP_ixproc <= br_x) &&
      (PP_iyproc > br_y) && bottom_edge) {
DEBUG(DBG_PARG("PP_iyproc"," %d",PP_iyproc));
DEBUG(DBG_PARG("mgmt_data"," %d",mgmt_data));    
    if ((PP_iyproc + 1 - mgmt_data) < br_y) 
      plural_memory[offset] = PP_iyproc - br_y + FREE_FLAG;
DEBUG(DBG_PARG("new_data"," %d",plural_memory[offset]));
  }
}


/*----------------------------------------------------------------------------*
 * Function   : identify_rectangle
 *
 * Parameters : int offset:	The slice of plural space we are trying to
 *				find a free rectangle in.
 *		int width:	The desired width of the rectangle
 *		int height:	The desired height of the rectangle
 *		int *br_x:	To return the x co-ord of bottom right corner
 *		int *br_y:	To return the y co-ord of bottom right corner
 *
 * Description: Attempts to find a free rectangle of the designated size in
 *		the offset slice of the plural space, returning the 
 *		co-ordinates of the bottom right corner in the two given
 *		parameters is successful and updating teh management data
 *		appropriately
 *
 * Result     : int : FAIL/SUCCESS
 *---------------------------------------------------------------------------*/

#ifdef __STDC__

int identify_rectangle( natural offset, natural width, natural height
			natural *br_x, natural *br_y )

#else

int identify_rectangle( offset, width, height, br_x, br_y )

natural offset;
natural width;
natural height;
natural *br_x;
natural *br_y;

#endif

{
  natural br_iproc;
  plural natural mgmt_data;
  plural natural br_corner;
  plural natural bottom_edge;
  plural natural right_edge = FALSE;
  plural char seg = ((PP_ixproc == (PP_nxproc - 1)) ? 1 : 0);
DBG_CALL("identify_rectangle");
DBG_ARGS(fprintf(dbg,"offset=%d, width=%d, height=%d, br_x=%x, br_y=%x", offset, width, height, br_x, br_y));

  mgmt_data = plural_memory[offset] & (~FREE_FLAG);

  bottom_edge = (mgmt_data >= height) && (plural_memory[offset] & FREE_FLAG);

  if (PP_ixproc < (PP_nxproc - 1))
    seg = bottom_edge && PP_xnetE(1).(!bottom_edge);

  if (bottom_edge) {

DEBUG(DBG_PARG("(bottom_edge) iproc","%d ",iproc));
    right_edge = scanAdd16u((plural natural) 1, seg) >= width;
  }

  br_corner = bottom_edge && right_edge;
  if (globalor(br_corner)) {

    if (br_corner) br_iproc = reduceMin16(PP_iproc);
    *br_x = br_iproc % PP_nxproc;
    *br_y = br_iproc / PP_nxproc;
    update_mgmt_data(offset,width,height,*br_x,*br_y);

DBG_EXIT(fprintf(dbg,"SUCCESS: *br_x=%d, *br_y=%d", *br_x, *br_y));
    return SUCCESS;
  }

  return FAIL;
}


/*----------------------------------------------------------------------------*
 * Function   : find_rectangle
 *
 * Parameters : int *offset:	To return the slice the rectangle is in
 *		int width:	The desired width of the rectangle
 *		int height:	The desired height of the rectangle
 *		int *br_x:	To return teh x co-ord of bottom right corner
 *		int *br_y:	To return the y co-ord of bottom right corner
 *
 * Description: Searches through the plural space, extending it if necessary,
 *		for a free rectangle of width x heigth PEs. The coords
 *		of the bottom right hand corner are returned in the two
 *		given parameters.
 *
 * Result     : int:	FAIL/SUCCESS
 *---------------------------------------------------------------------------*/

#ifdef __STDC__

natural find_rectangle( natural *offset, natural width, natural height, natural *br_x, natural *br_y )

#else

int find_rectangle( offset, width, height, br_x, br_y )

natural *offset;
natural width;
natural height;
natural *br_x;
natural *br_y;

#endif

{
DBG_CALL("find_rectangle");
DBG_ARGS(fprintf(dbg,"offset=%x, width=%d, height=%d, br_x=%x, br_y=%x",offset,width,height,br_x,br_y));

  *offset = TOP;
  
  while (*offset >= plural_space) {

    if ((*offset == plural_space) && (extend_plural_space() == FAIL)) {

DBG_FAIL(fprintf(dbg,"FAIL: Unable to extend plural space"));
      return FAIL;
    }

    if (identify_rectangle(*offset,width,height,br_x,br_y)) {
      
DBG_EXIT(fprintf(dbg,"SUCCESS: *offset=%d, *br_x=%d, *br_y=%d",*offset,*br_x,*br_y));
      return SUCCESS;
    }
    --(*offset);
  }

DBG_FAIL(fprintf(dbg,"FAIL: Never expected to get here"));
}
    

/*----------------------------------------------------------------------------*
 * Function   : find_space
 *
 * Parameters : *offset:	To pass back the offset in local memory
 *				the space is located at.
 *		int width:	Width of rectangular pe set
 *		int height:	Height of rectangular pe set
 *		int br_x:	X co-ord of bottom right corner of pe set
 *		int br_y:	Y co-ord of bottom right corner of pe set
 *
 * Description: searches for space in the plural space on the pes in
 *		the rectangular region sepcified. Extends the plural
 *		space if necessary, initilaises space to NIL and updates
 *		the management data where appropriate.
 *
 * Result     : natural :	SUCCESS - located space
 *				FAIL    - unable to locate sufficient space
 *---------------------------------------------------------------------------*/

#ifdef __STDC__

int find_space( natural *offset, natural width, natural height, natural br_x, natural br_y )

#else

int find_space( offset, width, height, br_x, br_y )

natural *offset;
natural width;
natural height;
natural br_x;
natural br_y;

#endif

{
  int got_some = FALSE;
DBG_CALL("find_space");
DBG_ARGS(fprintf(dbg,"offset=%x,width=%d,height=%d,br_x=%d,br_y=%d",offset,width,height,br_x,br_y));

  *offset = 1+stack_base;          /* Memory offset currently being examined */

  while ((*offset >= plural_space) && !got_some) { 
    
    (*offset)--;
DEBUG(fprintf(dbg,"*offset=%d",*offset));
    if ((*offset == plural_space) && (extend_plural_space() == FAIL)) {

DBG_FAIL(fprintf(dbg,"FAIL: Unable to extend space"));
      return FAIL;	
    }

    if ((PP_ixproc >= ((1 + br_x) - width))  && (PP_ixproc <= br_x) &&
	(PP_iyproc >= ((1 + br_y) - height)) && (PP_iyproc <= br_y)) {

DEBUG(DBG_PARG("iproc","%d ",iproc));
DEBUG(DBG_PARG("mgmt_data","%d ",plural_memory[*offset]));

      got_some = !globalor(!(plural_memory[*offset]&FREE_FLAG));
DEBUG(fprintf(dbg,"got_some=%d",got_some));
    }
  }
  
  update_mgmt_data(*offset,width,height,br_x,br_y);
DBG_EXIT(fprintf(dbg,"SUCCESS: *offset=%d",*offset));
  return SUCCESS;
}

/*----------------------------------------------------------------------------*
 * Function   : alloc_plural
 *
 * Parameters : object MPP_conform:	MP_Plural object new plural should
 *					conform to. Empty if creating new
 *					context
 *
 * Description: Either creates a new context, or creates a new plural in the
 *		given context. If a new context is eing created its description
 *		is passed back in MPC_conform and its size is specified by 
v *		length. 
 *		A new plural is characterised by its offset into the plural
 *		space and this is returned.
 *
 * Result     : natural:	Offset into plural space
 *				0 if unable to allocate
 *---------------------------------------------------------------------------*/

#ifdef __STDC__

natural alloc_plural( object MPC_conform )

#else

natural alloc_plural( MPC_conform )

object MPC_conform;

#endif

{
  natural offset;
DBG_CALL("alloc_plural");
DBG_ARGS(fprintf(dbg,"MPC_conform=%x",MPC_conform));

   if (OA_offset(MPC_conform) == 0) { /* Fresh context object */

     if (find_rectangle(&OA_offset(MPC_conform), OA_width(MPC_conform),
			OA_height(MPC_conform), &OA_br_x(MPC_conform),
			&OA_br_y(MPC_conform)) == FAIL) {

DBG_FAIL(fprintf(dbg,"FAIL: Unable to allocate plural space"));
       return FAIL;
     }
DBG_EXIT(fprintf(dbg,"SUCCESS: offset=%u, br_x=%u, br_y=%u",OA_offset(MPC_conform),OA_br_x(MPC_conform),OA_br_y(MPC_conform)));
     return SUCCESS;
   } 
  if (find_space(&offset, OA_width(MPC_conform), OA_height(MPC_conform),
		 OA_br_x(MPC_conform), OA_br_y(MPC_conform)) == FAIL) {
    
DBG_FAIL(fprintf(dbg,"FAIL: Unable to allocate plural space"));
    return FAIL;
  }
   
DBG_EXIT(fprintf(dbg,"%u",offset));
  return offset;
}

/*----------------------------------------------------------------------------*
 * Function   : scanaddy
 *
 * Parameters : plural natural val:	plural of 16-bit Nos to scan
 *		plural char segment:	segmentation (in y-axis)
 *
 * Description: Performs the same task as scanAdd16 but the operation is
 *  		done indepedently in each y column.
 *
 * Result     : plural natural: the result.
 *---------------------------------------------------------------------------*/

#ifdef __STDC__

plural natural scanaddy( plural natural val, plural char segment )

#else

plural natural scanaddy( val, segment )

plural natural val;
plural char segment;

#endif
		     
{
  plural natural sum = val;
  plural natural tmp;
  int step = 1;
  int i;

  while (step < PP_nyproc) {

    tmp=0;
    if (!segment) PP_xnetS(step).tmp = sum;
    if (!globalor(!segment)) break;
    segment = segment || PP_xnetS(step).segment;
    step = step*2;

  }

  return sum;
}




/*----------------------------------------------------------------------------*
 * Function   : mp_free_plurals
 *
 * Parameters : char *fe_address:	THe address of the beginning of a 
 *					list on the host of active plurals
 * 		int  no_of_plurals:	The number of entries in th list.
 *
 * Description: Pages in the front end list of active plurals and marks them as
 *		being active. Then scans through the plural space, making
 *		the management data correct and clearing the active flags for
 *		the next pass. Modifications to support GC protect stack
 *		the free plurals pass is only applied between TOP and
 *		stackbase if stackbase not equal to TOP.
 *
 * Result     : int:	SUCCESS - everything was groovy
 *			FAIL    - something strange and ungroovy happened
 *---------------------------------------------------------------------------*/

#ifdef __STDC__

visible int mp_free_plurals( char *fe_address, int no_of_plurals )

#else

visible int mp_free_plurals( fe_address, no_of_plurals )

char *fe_address;
int no_of_plurals;

#endif

{
  int ps_offset;		/* Offset into the plural space       */
  int page_no = 0;		/* Current fe plural list page number */
  object MPC_curr, MPC_next;    /* Current, next MasPar Context object*/
  object *P_MPC_curr;           /* Pointer to current MasPar Context  */
  plural char segments;         /* for scan operations                */
  plural natural potential_PE;
  plural natural tmp;
  natural new_plural_space = TOP;
  natural Bottom = (stack_base == TOP) ? plural_space : stack_base;
  int i;
  natural *page = (natural *) acu_scratch;  /* acu_scratch in 16-bit words */
  int page_offset;

DBG_CALL("free_plurals");
DBG_ARGS(fprintf(dbg,"fe_address=%x, no_of_plurals=%d, Bottom=", fe_address, no_of_plurals,Bottom);if (stack_base==TOP) fprintf(dbg,"plural_space(=%d)",plural_space);else fprintf(dbg,"stack_base(=%d)",stack_base));

DO_DEBUG(fprintf(stderr,"Bottom=%s(=%d)",((stack_base==TOP)?"plural_space":"stack_base"),((stack_base==TOP)?plural_space:stack_base)));

  /*  Step through entire plural space and mark as free */

  for (ps_offset = TOP; ps_offset > Bottom; ps_offset--) {

    tmp = plural_memory[ps_offset];
    tmp = tmp | FREE_FLAG;
    plural_memory[ps_offset] = tmp;
  }

  /*  Step through chain of MasPar Context objects and mark as being free */

  for (MPC_curr=MPC_chain; MPC_curr != NULL; MPC_curr = MPC_next) {
    
    MPC_next = OA_next(MPC_curr);
    OF_free(MPC_curr);
  }
  
  while (no_of_plurals > 0) {

    /* Page in plural list from host */

    if (copyIn(fe_address, acu_scratch, SCRATCH_MEMORY_SIZE) != 0) {

      mp_error = MP_COPY_IN_FAILED;
DBG_FAIL(fprintf(dbg,"FAIL: Error loading page %d",page_no));
      return FAIL;
    }

    /* update page orientated data */

    fe_address = fe_address + SCRATCH_MEMORY_SIZE;
    no_of_plurals = no_of_plurals - (SCRATCH_MEMORY_SIZE/(2*sizeof(natural)));
    page_offset = 0;
    page_no++;

    /*  for each offset,context_address pair in the page, mark the given
     *  area in the plural space as being not free
     */

    for (i=0; i < (SCRATCH_MEMORY_SIZE/(2*sizeof(natural)) +
	          ((no_of_plurals < 0) ? no_of_plurals : 0)); i++) {

      /* first 16-bit number is a context address, get hold of the context
       * and mark it as being not free. The second 16-bits are the offset */

      MPC_curr  = (object) *(page + page_offset);
      OM_not_free(MPC_curr);
	
      ps_offset = *(page + page_offset + 1);
      new_plural_space = (ps_offset < new_plural_space) ? ps_offset :
	new_plural_space;

      OM_with_context(MPC_curr) {
/*      if ((OA_start(MPC_curr) <= PP_iproc) &&
	  (PP_iproc < (OA_start(MPC_curr) + OA_length(MPC_curr)))) {
*/
	plural_memory[ps_offset] = plural_memory[ps_offset] & (~FREE_FLAG);
      }

      page_offset += 2;			         /* Next Context,Offset pair */
    }
  }

  /*  Now we need to go through all the MPC_contexts, free those which are
   *  "free" and mark all the plural space used by each context for it's
   *  context stack */

  for (P_MPC_curr = &MPC_chain; *P_MPC_curr != NULL; ) {

    MPC_curr = *P_MPC_curr;
    if (OM_freep(MPC_curr)) {

      OM_not_free(MPC_curr); /* To manipulate cannot be free! */
      *P_MPC_curr = OA_next(MPC_curr);
      OF_destroy(MPC_curr);
    }
    else {

      P_MPC_curr = &(OA_next(MPC_curr));
      OM_with_context(MPC_curr) {
/*      if ((OA_start(MPC_curr) <= PP_iproc) &&
	  (PP_iproc < (OA_start(MPC_curr) + OA_length(MPC_curr)))) {
*/
	new_plural_space = (OA_offset(MPC_curr) < new_plural_space) 
	  ? OA_offset(MPC_curr): new_plural_space;
	plural_memory[OA_offset(MPC_curr)] =
	  plural_memory[OA_offset(MPC_curr)] & (~FREE_FLAG);
      }
    }
  }
  
  /*  Now need to generate correct management data, each free slot, */
  /*  needs to have the number of contiguous pes are free above it  */

  for (ps_offset = TOP; ps_offset > Bottom; ps_offset--) {

    /*  Need to identify the "bottom" most PE of each FREE segment, my
     *  scan function uses this information to partition its operation
     *  into independent sets of processors
     */
    
    /* All PEs who are free and their down neighbour is not free */

    potential_PE = (plural_memory[ps_offset] & FREE_FLAG) == FREE_FLAG;
    segments = potential_PE && PP_xnetS(1).(!potential_PE);

    /* The bottom row is a special case as we cam't poll their down */
    /* neighbours */

    if (PP_iyproc == (PP_nyproc - 1)) segments = 0;

    PP_on_set() {

      if (potential_PE) {
      
	tmp = scanaddy((plural natural) 1,segments);
	plural_memory[ps_offset] = tmp | FREE_FLAG;
      }
    }
  }
  
  /*  If there isn't a GC Protect stack at the moment - probably unlikely
   *  but no harm in hoping, then we can take advantage of any "shrink"
   *  in the number of handles in theglobal environment
   */

  if (stack_base == TOP) {

    fprintf(stderr,"plural_space changed from %d to %d\n",plural_space,new_plural_space-1);
    plural_space = new_plural_space - 1;
  }
/*  mp_gc();*/

DBG_EXIT(fprintf(dbg,"SUCCESS"));
  return SUCCESS;
}
	           

